This application is directed to parallel processing switching networks and particularly to an improved multi-stage switch for interconnection of N system elements, where N can be several or thousands of computer processors or combinations of processors or other computer system elements. As a continuation, this disclosure relates specifically to an unbuffered switching system which operates asynchronously at each node of the network. With the improvements of this application the speed possibilities of the multi-stage switching network is improved by adding a high priority mode of interconnection in addition to the normal low priority mode of network interconnection, thus providing a single switching element to comprise a network capable of handling two different priorities of message transfers.
Multi-stage Switching Networks have become an accepted means for interconnecting multiple devices within a computer system. Often systems require multiple paths through the switching networks to perform different functions. In earlier work at IBM by Peter Franaszek entitled "Path Hierarchies in Interconnection Networks" (IBM Journal of Research and Development, Volume 31, Number 1, January, 1987), Franaszek described some of the problems associated with interconnection networks for high performance multiprocessor systems. In the paper it was a proposal of a network structure which optimized the delays of each network function by separation of the control flow from data flow and by transferring control information through a hierarchy of physical paths with varying speeds. The recommendation was for an implementation of a hierarchial control network utilizing a crosspoint chip.
Franaszek and Georgio continued this work with a patent, "Multipath Hierarchies in Interconnection Networks"; U.S. Pat. No. 4,952,930 issued Aug. 28, 1990, and described two hierarchical paths, one providing low-latency message transfer and the other providing guaranteed-delivery of a message transfer a longer latency.
A problem recognized in the work was that blocking in multistage networks, namely the limitations of data transfer delays between stages and contention resolution delays at each stage of a network have been substantial performance problems. In order to avoid or reduce the blocking, a hierarchical proposal of two networks only, each with a different latency period. The first network being unbuffered for low latency, and the second network being buffered for store and forward use would provide the guaranteed delivery of a message under all traffic conditions. A message is attempted over the low-latency path first. If the transmission fails due to blocking or contention, it is retransmitted over the guaranteed-delivery path. This allows usually about 90% of the messages to be sent successfully over the low-latency path, and guarantees the delivery of a message that gets blocked on the low-latency path due to retransmissions.
A problem arises with the use of multiple paths; i.e., as systems get larger and larger in terms of the number of devices that have to be interconnected, the massive amount of interconnects becomes a major problem and expense. Increasing the number of interconnecting networks becomes a major factor of two or more to provide for multiple paths vastly adds to this problem. It is not uncommon for modern parallel processors to be configured for hooking thousands of processors to thousands of memory modules; the interconnection problem for such solutions is immense.
We have solved some of the problems encountered in the prior art which we referred to above and will describe in the detailed description a way whereby multiple functions can be transmitted over the same network path.
In making our invention we recognize that others have tackled various problems in the network area. Some of this literature is discussed here.
U.S. Pat. No. 4,679,190, issued Jul. 7, 1987, to Dias et al, described a method of delivery of high priority messages in a multi-stage network using a multi-stage interconnection connector for voice and data packets. This patent relates to a different transmission scheme with synchronous, clocked, time-slotted transmission. There is no control by a Hi/Lo priority interface line, and the relatively complex method of performing priority and switch connections is different and applicable only to 2.times.2 sub-switches only. The priority levels were encoded on the data lines.
U.S. Pat. No. 4,821,258, issued Apr. 11, 1989 to Alexander G. Fraser described a packet switching system in which access to the same output bus, when there is contention, is determined by priority, permitting only one data packet token access to the single bus. This is a different telephone transmission scheme which is synchronous, clocked and time slotted, and not controlled by a Hi/Lo priority interface line. This is a buffered switch which requires data FIFO. The priority levels are encoded on the data lines, and there is a complex logic and switch addressing scheme required for implementation. The system has no capability to terminate from a sending device.
U.S. Pat. No. 4,667,323, issued May 19, 1987, to Engdahl et al. described a network with high and low priority messages on a single ring data path, but apparently also contemplated a similar function with trunk, star and ethernet topology. The scheme used station token holding, and no switch was involved. The present application relates to multi-stage switching networks.
Again one must understand that buses also have priority schemes. For instance, representative of such a bus priority scheme is U.S. Pat. No. 4,670,855, issued Jun. 2, 1987, to Caprio et al, described an interchangeable interface circuit card, which based upon priority, determines which one of a number of interchangeable interface circuit cards used for determining control of a common data path based on priority will be permitted to control the path.
U.S. Pat. No. 4,623,886, issued Nov. 18, 1986, to William D. Livingston described a network communication system with techniques for handling priority message transmission to ensure that higher priority data is transmitted before lower priority data with bus interface units which dynamically determine which information is used.
U.S. Pat. No. 4,213,201, issued Jul. 15, 1990, to Gagnier et al described generally a switching network for multistage systems in which a scheme for handling priority messages was used.
U.S. Pat. No. 4,663,620, issued May 5, 1987, to Paul et all described a modified crossbar switch in which a fixed priority conflict resolution is implemented together with random restrain on the side of (the) participating processors by implementing a threshold at each processor such that there exists a bias created in favor of the lowest priority processor of an effective parallel computer.
As the object includes a way to assign a different priority level to each of multiple functions, and to allow each function to be transmitted over the same path, it may be useful to review some of the IBM Technical Disclosure Bulletins which generally relate to switches. Token ring structures have been suggested in lieu of a tree to prioritize functions of a network. With the scheme of H. S. Stone, a combining switch was suggested to allow tree and token ring networks to manage a priority among nodes so that a network could detect one request from among N Messages, and broadcast that transaction to all processors by selection and broadcast. A detailed prioritization of request scheme was employed. A first publication was made in the IBM T.D.B. in H. S. Stone's work on synchronization of processors, and memories, and related switch work was also published in the IBM T.D.B. in Vol. 32. No. 1, June 1989, pp 281 et seq. as "ENHANCED MEANS (a fetch-and-add instruction) FOR PARALLEL SYNCHRONIZATION IN CROSSBAR SWITCHING NETWORKS".
This scheme was enhanced and published in the IBM T.D.B. of Vol. 32, No. 4A, September 1989, under the titles which included, pp 225 et seq. "LOW-COST COMBINING SWITCH THAT IMPLEMENTS A MULTIPROCESSOR JOIN". In that same IBM TDB in the article called "PRIORITY-RESOLUTION MECHANISM FOR REDUCING COLLISIONS IN A MULTI-PROCESSOR INTERCONNECTION NETWORK" H. S. Stone proposed, pp 338 et seq. a priority resolution mechanism in the form of a switching node which arbitrated requests for memory access according to a rotated order of memory module numbers. The Fetch-and Add synchronization instruction was discussed by Franaszek, Heidelberger and Stone on pp 259 of this Volume in the article called "PARALLEL SYNCHRONIZATION WITH HARDWARE COLLISION DETECTION AND SOFTWARE COMBINING".
The synchronization of parallel processors and memories continued to be discussed in the TDBs in Vol 32, under No. 8B, January 1990 in the article called "TECHNIQUE FOR PRIORITY RESOLUTION IN NETWORKS THAT SUPPORT PARALLEL SYNCHRONIZATION".
Data switching networks (such as that covered by the IEEE 896 'Futurebus) are applicable to many applications such as communications between processors in a multiprocessor system where a single bus is insufficient to carry the required traffic, and in parallel processing situations. The basic need for a solution was recognized in IBM Technical Disclosure Bulletin Vol. 31, No. 9, February 1989 by D. M. Taub--See "DATA-SWITCHING NETWORK FOR A MAGNETIC DISC STORAGE SYSTEM". However, the Futurebus technology contemplated required some sort of control acquisition arbitration scheme as described therein. This type of thing is inapplicable when the present class of improvements described here and in related applications is employed.
A problem existed in these prior art references in that in order to handle the needs of a few or thousands of processors with a switching network there is a requirement for the ability to dynamically and quickly establish and break element interconnections, to do it cheaply and easily, desirably in one chip. In order to have the expandability to many thousands of elements, to permit any length, with a non-calibrated interconnection of wire lengths, and to allow solutions to distributed processing systems, and allow for future frequency increases, it is necessary to design an apparatus which allows parallel establishment and data transfer over N switching paths simultaneously.